package com.zrkizzy.linkedlist;

import java.util.Stack;

/**
 * 24. 两两交换链表中的节点<br/>
 * https://leetcode.cn/problems/swap-nodes-in-pairs/description/
 *
 * @author zhangrongkang
 * @date 2022/11/16
 */
public class 两两交换链表中的节点 {
    class ListNode {
        int val;
        ListNode next;

        ListNode() {}

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }


    class Solution {
        // 辅助栈 + 迭代：将两个节点作为一个整体同时入栈和出栈
        public ListNode swapPairs(ListNode head) {
            // 特殊情况
            if (head == null || head.next == null) {
                return head;
            }
            Stack<ListNode> stack = new Stack<>();
            // 定义新的链表用于返回
            ListNode link = new ListNode(0), result = link;
            while (head != null && head.next != null) {
                // 将当前节点和下一个节点都添加到栈中
                stack.push(head);
                stack.push(head.next);
                // 将节点添加到栈中以后就应当立刻移动节点，因为栈中的元素此时仍然是节点的内存地址，修改link.next的同时也在修改当前的head
                // 将迭代的链表向后移动两个单位
                head = head.next.next;
                // 利用后进先出的原则将节点进行连接
                link.next = stack.pop();
                // 向后移动
                link = link.next;
                link.next = stack.pop();
                // 当前链表继续向后移动
                link = link.next;
            }
            // 如果链表长度为奇数，最后一个单位长度则会遗漏
            link.next = head;

            return result.next;
        }
    }
}
